package binaryTree;

public class MaxBinaryTree19 {

    public TreeNode constructMaximumBinaryTree(int[] nums) {

        if (nums.length==0){
            return null;
        }
        int index;
        int max=0;
        int max_index=0;

        for (index= 0; index < nums.length; index++) {
            if (nums[index]>max){
                max=nums[index];
                max_index=index;
            }
        }
        TreeNode root=new TreeNode(max);
        if (nums.length==1){
            return  root;
        }

        int[] leftPart= new int[max_index];
        int[]  rightPart=new int[nums.length- leftPart.length-1];
        int m=0;
        int n=0;

        for (int i = 0; i < nums.length; i++) {
            if ( i<max_index&&m< leftPart.length){
                leftPart[m]=nums[i];
                m++;
            }
          if (i==max_index){
                continue;
            }
        if (i>max_index &&n< rightPart.length){
            rightPart[n]=nums[i];
            n++;
        }
        }

        root.left=constructMaximumBinaryTree(leftPart);
        root.right=constructMaximumBinaryTree(rightPart);
        return  root;
    }

//注意类似用数组构造二叉树的题目，每次分隔尽量不要定义新的数组，而是通过下标索引直接在原数组上操作，
// 这样可以节约时间和空间上的开销。
//
//一些同学也会疑惑，什么时候递归函数前面加if，什么时候不加if，这个问题我在最后也给出了解释。
//
//其实就是不同代码风格的实现，一般情况来说：如果让空节点（空指针）进入递归，就不加if，
// 如果不让空节点进入递归，就加if限制一下， 终止条件也会相应的调整。

    public TreeNode constructMaximumBinaryTree0(int[] nums) {
        return constructMaximumBinaryTree1(nums, 0, nums.length);
    }

    public TreeNode constructMaximumBinaryTree1(int[] nums, int leftIndex, int rightIndex) {
        if (rightIndex - leftIndex < 1) {// 没有元素了
            return null;
        }
        if (rightIndex - leftIndex == 1) {// 只有一个元素
            return new TreeNode(nums[leftIndex]);
        }
        int maxIndex = leftIndex;// 最大值所在位置
        int maxVal = nums[maxIndex];// 最大值
        for (int i = leftIndex + 1; i < rightIndex; i++) {
            if (nums[i] > maxVal){
                maxVal = nums[i];
                maxIndex = i;
            }
        }
        TreeNode root = new TreeNode(maxVal);
        // 根据maxIndex划分左右子树
        root.left = constructMaximumBinaryTree1(nums, leftIndex, maxIndex);
        root.right = constructMaximumBinaryTree1(nums, maxIndex + 1, rightIndex);
        return root;
    }

    public static void main(String[] args) {
        MaxBinaryTree19 maxBinaryTree19 = new MaxBinaryTree19();
        int[]  nums={3,2,1};
        TreeNode treeNode = maxBinaryTree19.constructMaximumBinaryTree0(nums);

    }
}
